class Solution:
    def backtracking(self, nums, target, remain, ans):
        self.cnt += 1
        if remain == 0:
            if ans < target:
                self.ans = max(ans, self.ans)
            return

        for i in range(len(nums)):
            tmp = ans * 10 + nums[i]
            self.backtracking(nums, target, remain-1, tmp)

    def maxNumber(self, nums, target):
        self.cnt = 0
        nums.sort(reverse=True)
        self.ans = 0
        num_len = len(str(target))

        min_val = nums[-1] * (10 ** (num_len-1))
        if min_val > target:           
            ans = nums[0]
            for i in range(num_len-2):
                ans = ans * 10 + nums[0]
            return ans
        self.backtracking(nums, target, num_len, 0)
        return self.ans


if __name__ == '__main__':
    print("字节1")
    notice = '''
\t给定一个数组，给定一个数字，,用数组中的数字，组成一个最大且小于目标数的数字。
例如给定{2,3,1}, 25632，返回23333'''
    print(notice)

    cases = {
        132: [8,],
        456: [2, 3, 1],
        25632: [2, 3, 1],
        98765432: [8,2, 3, 1],
        5012: [3, 4, 5],
        1012: [3, 4, 5],
        4111: [3, 4, 5],
        3453: [3, 4, 5],
    }

    for k, v in cases.items():
        s = Solution()
        ans = s.maxNumber(v, k)
        print('case {}, {}: {}'.format(v, k, ans))

